package com.bootcamp.s2_0922.ds._0927;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @program: myClassCode
 * @description: delete a node in BST
 * @author: Keyu Li
 * @create: 2021-09-27 09:38
 **/

public class Demo1_MyBST {
    public static void main(String[] args) {
        Tree<Integer> integerTree = new Tree<>();
        /**
         * this tree:

         *        .-9---.
         *       /       \
         *      3      .-20-.
         *    / \     /      \
         *   1  7    15      25
         *      \   / \       \
         *      8  14 18      30
         *         /   \     / \
         *        12   19   29 35
         *        \        /
         *        13      28
         *                /
         *              26
         */
        ArrayList<Integer> preOrder = new ArrayList<>();
        ArrayList<Integer> inOrder = new ArrayList<>();
        // preorder list
        preOrder.add(9);
        preOrder.add(3);
        preOrder.add(1);
        preOrder.add(7);
        preOrder.add(8);
        preOrder.add(20);
        preOrder.add(15);
        preOrder.add(14);
        preOrder.add(12);
        preOrder.add(13);
        preOrder.add(18);
        preOrder.add(25);
        preOrder.add(30);
        preOrder.add(29);
        preOrder.add(28);
        preOrder.add(26);
        preOrder.add(35);
        // inorder list
        inOrder.add(1);
        inOrder.add(3);
        inOrder.add(7);
        inOrder.add(8);
        inOrder.add(9);
        inOrder.add(12);
        inOrder.add(13);
        inOrder.add(14);
        inOrder.add(15);
        inOrder.add(18);
        inOrder.add(20);
        inOrder.add(25);
        inOrder.add(26);
        inOrder.add(28);
        inOrder.add(29);
        inOrder.add(30);
        inOrder.add(35);
        // create tree
        integerTree.buildTreeByPreAndInOrder(preOrder, inOrder);
        System.out.println(integerTree.root.value);
        TreePrinter.print(integerTree.root);
        // preorder traverse
        System.out.println(integerTree.preOrder());
        System.out.println(integerTree.postOrder());
        System.out.println(integerTree.inOrder());
        System.out.println(integerTree.inOrderMorris());
        System.out.println(integerTree.inOrderEx());
        System.out.println(integerTree.preOrderMorris());
        System.out.println(integerTree.preOrderAnotherMorris());
        // get min difference
        int minDiff1 = integerTree.getMinDiffByInOrder();
        int minDiff2 = integerTree.getMinDiffRecur();
        System.out.println(minDiff1);
        System.out.println(minDiff2);
    }
}

class Tree<T extends Comparable<T>> {
    TreeNode root;
    int size;

    class TreeNode implements TreePrinter.PrintableNode {
        T value;
        TreeNode lchild;
        TreeNode rchild;

        public TreeNode(T value, TreeNode lchild, TreeNode rchild) {
            this.value = value;
            this.lchild = lchild;
            this.rchild = rchild;
        }

        @Override
        public TreePrinter.PrintableNode getLeft() {
            return this.lchild;
        }

        @Override
        public TreePrinter.PrintableNode getRight() {
            return this.rchild;
        }

        @Override
        public String getText() {
            return String.valueOf(this.value);
        }
    }

    public Tree() {
        this.root = null;
        size = 0;
    }

    public boolean add(T newValue) {
        if (root == null) {
            root = new TreeNode(newValue, null, null);
            size++;
            return true;
        }
        TreeNode curr = root;
        TreeNode currF = null;
        boolean insertLeft = false;
        while (curr != null) {
            int com = newValue.compareTo((T) curr.value);
            if (com < 0) {
                currF = curr;
                curr = curr.lchild;
                insertLeft = true;
            } else if (com > 0) {
                currF = curr;
                curr = curr.rchild;
                insertLeft = false;
            } else
                throw new RuntimeException("cannot add same value node!");
        }
        curr = new TreeNode(newValue, null, null);
        if (insertLeft) currF.lchild = curr;
        else currF.rchild = curr;
        size++;
        return true;
    }


    public boolean deleteNode(T delValue) {
        // iterate and get the node with same value
        TreeNode curr = root;
        TreeNode currF = null;
        while (curr != null) {
            int com = delValue.compareTo((T) curr.value);
            if (com == 0)
                break;
            if (com > 0) {
                currF = curr;
                curr = curr.lchild;
            } else {
                currF = curr;
                curr = curr.rchild;
            }
        }
        // if curr is null, indicate not found
        if (curr == null) return false;
        // now we got the delete node
        // if the delete node has two children,
        // then switch this node to a single child node, or leaf node, from left to right.
        if (curr.lchild != null && curr.rchild != null) {
            TreeNode beReplaced = curr;
            curr = curr.lchild;
            while (curr.rchild != null) {
                currF = curr;
                curr = curr.rchild;
            }
            beReplaced.value = curr.value;
        }
        // now delete the node
        // first, when the delete node is root
        if (currF == null) {
            size--;
            root = curr;
            return true;
        }
        return true;
    }

    /**
     * preorder, inorder, postorder iterate
     */
    // root first order iterate
    public ArrayList<T> preOrder() {
        ArrayList<T> preList = new ArrayList<>();
        Stack<TreeNode> nodes = new Stack<>();
        nodes.push(root);
        while (!nodes.isEmpty()) {
            TreeNode curr = nodes.pop();
            preList.add(curr.value);
            if (curr.rchild != null) nodes.push(curr.rchild);
            if (curr.lchild != null) nodes.push(curr.lchild);
        }
        return preList;
    }

    // root first order recursive
    public ArrayList<T> preOrderRecur() {
        ArrayList<T> preList = new ArrayList<>();
        preOrderRecurHelper(root, preList);
        return preList;
    }

    private void preOrderRecurHelper(TreeNode curr, ArrayList<T> preList) {
        if (curr == null) return;
        preList.add(curr.value);
        preOrderRecurHelper(curr.lchild, preList);
        preOrderRecurHelper(curr.rchild, preList);
    }

    // root-last order iterate by stack
    public ArrayList postOrder() {
        ArrayList<T> list = new ArrayList<>();
        Stack<TreeNode> nodes = new Stack<>();
        nodes.push(root);
        while (!nodes.isEmpty()) {
            TreeNode curr = nodes.pop();
            list.add(0, curr.value);
            if (curr.lchild != null)
                nodes.push(curr.lchild);
            if (curr.rchild != null)
                nodes.push(curr.rchild);
        }
        return list;
    }


    // recursive method
    public ArrayList<T> postOrderRecur() {
        ArrayList<T> postList = new ArrayList<>();
        postOrderRecurHelper(root, postList);
        return postList;
    }

    private void postOrderRecurHelper(TreeNode node, ArrayList<T> postList) {
        if (node == null) return;
        postOrderRecurHelper(node.lchild, postList);
        postOrderRecurHelper(node.rchild, postList);
        postList.add((T) node.value);
        return;
    }

    // inorder iterate
    public ArrayList inOrder() {
        ArrayList<T> list = new ArrayList<>();
        Stack<TreeNode> nodes = new Stack<>();
        TreeNode curr = root;
//        nodes.push(curr);
        while (!nodes.isEmpty() || curr != null) {
            while (curr != null) {
                nodes.push(curr);
                curr = curr.lchild;
            }
            curr = nodes.pop();
            list.add(curr.value);
            curr = curr.rchild;
        }
        return list;
    }

    // Morris iteration method
    public ArrayList inOrderMorris() {
        ArrayList<T> list = new ArrayList<>();
        TreeNode curr = root;
        TreeNode pre;
        while (curr != null) {
            if (curr.lchild != null) {
                pre = curr.lchild;
                while (pre.rchild != null && pre.rchild != curr)
                    pre = pre.rchild;
                if (pre.rchild == null) {
                    pre.rchild = curr;
                    curr = curr.lchild;
                } else {
                    pre.rchild = null;
                    list.add(curr.value);
                    curr = curr.rchild;
                }
            } else {
                list.add(curr.value);
                curr = curr.rchild;
            }
        }
        return list;
    }

    // recursive method
    public ArrayList<T> inOrderRecur() {
        ArrayList<T> inList = new ArrayList<>();
        inOrderRecurHelper(root, inList);
        return inList;
    }

    private void inOrderRecurHelper(TreeNode node, ArrayList<T> inList) {
        if (node == null) return;
        inOrderRecurHelper(node.lchild, inList);
        inList.add((T) node.value);
        inOrderRecurHelper(node.rchild, inList);
    }

    // level order iterator
    public void levelOrder() {
        ArrayList<T> levelList = new ArrayList<>();

    }

    /**
     * create tree through inorder and postorder iteration
     */
    public void buildTreeByPostAndInOrder(List<T> inList, List<T> postList) {
        root = buildTreePostRecurHelper(inList, postList);
        size = inList.size();
        return;
    }

    private TreeNode buildTreePostRecurHelper(List<T> inList, List<T> postList) {
        // get root from post order
        int listSize = inList.size();
        // when there is no node exist:
        if (listSize == 0) return null;
        // else, create this node:
        TreeNode curr = new TreeNode(postList.get(listSize - 1), null, null);
        // when only one node  exist, return
        if (listSize == 1) return curr;
        // get the index of root in in order
        int index = inList.indexOf(curr.value);
        // inorder   left tree: 0 -- index-1, right tree: index+1 -- size-1
        // postorder left tree: 0 -- index-1, right tree: index -- size-2
        // sublist contains left index and omit right index.
        curr.lchild = buildTreePostRecurHelper(inList.subList(0, index), postList.subList(0, index));
        curr.rchild = buildTreePostRecurHelper(inList.subList(index + 1, listSize), postList.subList(index, listSize - 1));
        return curr;
    }

    /**
     * create tree by preorder and inorder
     */
    public void buildTreeByPreAndInOrder(List<T> preList, List<T> inList) {
        root = buildTreePreRecurHelper(preList, inList);
        size = preList.size();
    }

    private TreeNode buildTreePreRecurHelper(List<T> preList, List<T> inList) {
        int listSize = preList.size();
        if (listSize == 0) return null;
        TreeNode curr = new TreeNode(preList.get(0), null, null);
        if (listSize == 1) return curr;
        int index = inList.indexOf(curr.value);
        // 左右子节点遍历
        curr.lchild = buildTreePreRecurHelper(preList.subList(1, index + 1), inList.subList(0, index));
        curr.rchild = buildTreePreRecurHelper(preList.subList(index + 1, listSize), inList.subList(index + 1, listSize));
        return curr;
    }

    public int getMinDiffRecur() {
        if (size == 1) throw new RuntimeException("only one node exist!");
        return getMinDiffRecurHelper(root);
    }

    private int getMinDiffRecurHelper(TreeNode curr) {
        // 该节点给叶子节点，可认为当前节点最小值为int最大值
        if (curr.lchild == null && curr.rchild == null)
            return Integer.MAX_VALUE;
        // 当前节点只有一个子树，当前节点最小值为 当前节点与该子树最大/小值之差，再同子节点最小值比较
        int currValue = (Integer) curr.value;
        if (curr.rchild == null) {
            int min = currValue - getLeftMaxHelper(curr.lchild);
            int minLeft = getMinDiffRecurHelper(curr.lchild);
            return min < minLeft ? min : minLeft;
        }
        if (curr.lchild == null) {
            int min = getRightMinHelper(curr.rchild) - currValue;
            int minRight = getMinDiffRecurHelper(curr.rchild);
            return min < minRight ? min : minRight;
        }
        // 当前节点有两个子树，当前节点最小值为与左子树最大值，右子树最小值 之差的最小值，再同子节点最小值比较
        int leftMax = getLeftMaxHelper(curr.lchild);
        int rightMin = getRightMinHelper(curr.rchild);
        int min = leftMax + rightMin > 2 * currValue ? currValue - leftMax : rightMin - currValue;
        int minLeft = getMinDiffRecurHelper(curr.lchild);
        int minRight = getMinDiffRecurHelper(curr.rchild);
        min = min < minLeft ? min : minLeft;
        return min < minRight ? min : minRight;
    }

    private int getRightMinHelper(TreeNode curr) {
        while (curr.lchild != null)
            curr = curr.lchild;
        return (Integer) curr.value;
    }

    private int getLeftMaxHelper(TreeNode curr) {
        while (curr.rchild != null)
            curr = curr.rchild;
        return (Integer) curr.value;
    }

    // 方法二：二叉搜索树中序遍历为递增序列，最小之差一定发生在相邻节点之间，比较相邻节点差的最小值
    public int getMinDiffByInOrder() {
        ArrayList<T> inOrderList = inOrder();
        if (size == 1) throw new RuntimeException("only one node exist!");
        int min = (Integer) inOrderList.get(1) - (Integer) inOrderList.get(0);
        for (int i = 1; i < size; i++) {
            int minTemp = (Integer) inOrderList.get(i) - (Integer) inOrderList.get(i - 1);
            min = min < minTemp ? min : minTemp;
        }
        return min;
    }

    public ArrayList inOrderEx() {
        TreeNode curr = root;
        TreeNode pre;
        ArrayList<T> list = new ArrayList<>();
        while (curr != null) {
            // if curr has left node
            if (curr.lchild != null) {
                // find pre node
                pre = curr.lchild;
                while (pre.rchild != null && pre.rchild != curr)
                    pre = pre.rchild;
                if (pre.rchild == null) {
                    // if pre has no right node, add curr
                    pre.rchild = curr;
                    curr = curr.lchild;
                } else {
                    // else, cut the link
                    list.add(curr.value);
                    curr = curr.rchild;
                    pre.rchild = null;
                }

            } else {
                list.add(curr.value);
                curr = curr.rchild;
            }
        }
        return list;
    }

    public ArrayList preOrderMorris() {
        ArrayList<T> list = new ArrayList<>();
        TreeNode curr = root;
        TreeNode pre = null;
        while (curr != null) {
            if (curr.lchild != null) {
                pre = curr.lchild;
                while (pre.rchild != null && pre.rchild != curr)
                    pre = pre.rchild;
                if (pre.rchild == null) {
                    pre.rchild = curr;
                    list.add(curr.value);
                    curr = curr.lchild;
                } else {
                    curr = curr.rchild;
                    pre.rchild = null;
                }
            } else {
                list.add(curr.value);
                curr = curr.rchild;
            }
        }
        return list;
    }

    public ArrayList preOrderAnotherMorris() {
        ArrayList<T> list = new ArrayList<>();
        TreeNode curr = root;
        TreeNode pre = null;
        while (curr != null) {
            if (curr.lchild != null) {
                pre = curr.lchild;
                while (pre.rchild != null && pre.rchild != curr.rchild)
                    pre = pre.rchild;
                if (pre.rchild == null) {
                    pre.rchild = curr.rchild;
                    list.add(curr.value);
                    curr = curr.lchild;
                } else {
                    curr = curr.lchild;
                    pre.rchild = null;
                }
            } else {
                list.add(curr.value);
                curr = curr.rchild;
            }
        }
        return list;
    }
}

